Graphics Plus

home *** CD-ROM | disk | FTP | other *** search

/ Graphics Plus / Graphics Plus.iso / info / rtnews / rtnews3 < prev next >

Wrap

Text File | 1994-10-16 | 46.9 KB | 1,216 lines

_ __ ______ _ __ ' ) ) / ' ) ) /--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _ / \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_</_(_(_/_/_)_ / /| ' |/ "Light Makes Right" April 6, 1988 Compiled by Eric Haines, 3D/Eye Inc, ...!hplabs!hpfcla!hpfcrs!eye!erich All contents are US copyright (c) 1988 by the individual authors New Distributor Address ----------------------- I have been trying to switch over to something faster, cheaper, and more reliable than uucp mail. As you (hopefully) know, I have sent you test messages, to which about 2/3rds the mailing list has replied. If you receive this issue of the RT News with a return address of "...!eye!erich", then I have NOT received your reply. Write to: saponara@tcgould.tn.cornell.edu Those who have successfully replied will get it with the "saponara" return address. Please consider "...!eye!erich" to still be my mailing address - the other account is "on loan" and may disappear someday. By the way, the new mailing list is attached at the end of this issue. -- Eric ----- Contents: RT News, hardcopy form (Andrew Glassner) node changes (Paul Heckbert & Brian Barsky, Darwyn Peachey) new members (Cary Scofield, Michael Cohen, John Chapman) question for the day (Rod Bogart) Re: Linear-time voxel walking for BSP (Erik Jansen) some thoughts on the theory of RT efficiency (Jim Arvo) Automatic Creation of Object Hierarchies for Ray Tracing (Eric Haines) Best of USENET (Tait Cyrus, Todd Elvins) ----------------------------------------------------------------------------- from: Andrew Glassner subject: RT News, hardcopy form I was surprised that there are still some folks on the softcopy list not on the hardcopy list. On the next mailing, please ask anyone on the electronic list who isn't getting the hardcopy (but wants to) to drop me a line, electronically (glassner@cs.unc.edu) or physically at the Department of Computer Science, UNC-CH, Chapel Hill, NC 27599-3175. -Andrew ----------------------------------------------------------------------------- subject: node changes [the gist: change the net addresses of Brian Barsky, Paul Heckbert, Don Marsh, and Michael Hohmeyer's "degas" node to "miro". Change Darwyn Peachey to Pixar] from: Paul Heckbert My net address is changing from ph@degas.berkeley.edu to ph@miro.berkeley.edu (we're switching from an impressionist to a more modern artist) Although the machine "degas" is being phased out, mail to my old address should continue to reach me, but the new address is faster and more reliable. from: Brian Barsky Degas is going away. Mail should get to me as "barsky@berkeley.edu" on the ARPAnet and as "...ucbvax!barsky" on Usenet. My machine is "beta", but that shouldn't be necessary in the address. from: Darwyn Peachey Change of address: pixar!peachey@ucbvax.Berkeley.EDU - or - {sun,ucbvax}!pixar!peachey ----------------------------------------------------------------------------- subject: new people from: Cary Scofield Please add my name to the Ray Tracing News mailing list. You can use the same address(es) you use for Jim Arvo or Olin Lathrop or the one I give you below. I really enjoy reading RTN -- very enlightening stuff! Thanks, Cary Scofield Apollo Computer Inc. 270 Billerica Rd. Chelmsford MA 01824 apollo!scofield@eddie.mit.edu > Could you please write up a paragraph about yourself which I > could include next issue as an introduction? I don't know that there is much about myself worth talking about, but here goes ... I've been working off-and-on with 3D graphics applications and systems for about 9 years ... started at Apollo 4 1/2 years ago ... been working on Apollo's 3dGMR and Raytracer packages ... presently in part-time pursuit of an MS in Systems Engineering at Boston Univ. ... my prevailing interests nowadays are in finding and developing a suitable software architecture for an image sythesis system that is network-distributable and user-extensible. - Cary Scofield ------- from: John Chapman [John is presently doing grad. work in computer graphics] Yes I'd like to be on the list - getting the back issues would be great, thanks! The most stable email address for me is: ...!ubc-cs!fornax!sfu_cmpt!chapman although this may change shortly nothing sent to it will be lost. Fastest response address for short notes is still ...fornax!bby-bc!john -------- from: Eric Haines Michael Cohen has also been added to the list. He should be well known to anyone who has read anything about radiosity, and has also done work in ray tracing (his latest efforts with John Wallace resulting in an algorithm for combining radiosity and ray tracing [Siggraph '87, last article]). In 1983 we both entered the Program of Computer Graphics at Cornell, and after graduation he stayed on as a professor. Embarrassingly enough, I thought that he was on the RT News mailing list (most of the PCG staff are) - anyway, he's been added: cohen@squid.tn.cornell.edu ----------------------------------------------------------------------------- subject: question for the day from: Rod Bogart I actually do have a ray tracing question. There has been mucho noise on the net about "point in poly". Around here, we raytrace triangles. So, what is the fastest reliable way to intersect a ray with a triangle and also get back barycentric coordinates? We subdivide our B-spline patches into a hierarchy of bounding volumes with triangles at the leaves. We preprocess the triangles by calculating a matrix to aid the intersection process. The problem is, the matrix must be inverted, and doesn't always cooperate (this usually fails for triangles nearly aligned with a coordinate plane). Is there a favorite way of storing a triangle (instead of our failing matrix) so that the intersection returns barycentric coordinates (r,s,t) all 0 to 1? You don't need to bother the rest of the RT gang, if you have solution of which you are confident. Thanks, RGB ----------------------------------------------------------------------------- From: erik jansen Subject: Re: Linear-time voxel walking for BSP I have some experience with the 'recursive' ray traversal (as I called it) described by Jim Arvo. The first implementation dates from fall'83 (as mentioned in the previous RT news). I presented the idea during the workshop 'Data structures for raster graphics' (June 1985) and I compared it there with the 'sequential' traversal and did the suggestion that both methods can also be applied to a hierarchical box structure. See: F.W. Jansen, 'Data structures for ray tracing', In: 'Data structures for raster graphics', Proceedings workshop, Kessener, L.R.A, Peters, F.J., Lierop, M.L.P. van, eds., 57-73, Eurographics Seminars, Springer Verlag, 1986. In my thesis 'Solid modeling with faceted primitives', (Sept. 1987) it is discussed on the pages 63-66. I agree that these sources are rather obscure and not known to people (let say) outside the Netherlands. Here follows a summary of the pages of my thesis: The (sequential) ray tracing algorithm for the (BSP) cell structure proceeds by local access. First the intersection of the ray with the total structure is calculated, then the cells are stepwise traversed by calculating the intersection of the ray with the cell planes and determining which cell is traversed next. The spatial index (directory) is used to access the data in the cell. (..). The index in the directory is found by an address computation on the coordinates of a query point (for all points within a cell, the address computation function gives the same index value) (This is the EXCELL directory method see Tamminen Siggraph'83). A similar method is described in [Fujimoto et al., 1986] for traversing an octree space subdivision: a neighbour finding technique on the basis of octree indexes. Both methods are better than the method described in [Glassner, 1984], which classifies each point by descending the complete octree. (..) Another method is feasible: a tree traversal method for the cell structure. This method uses a cell structure that is created by a binary subdivision. This recursive ray traversal method intersects the cell structure and recursively subdivides the ray and proceeds with the partitioning (collection of cells) first intersected. If the ray interval only intersects a single cell then the data in that cell is tested for intersection with the ray. (..) Both algorithms have been implemented but no clear differences in performance could be found: the average number of cells traversed for each ray is more than two or three, which would be beneficial for the sequential traversal, but it is not large enough to justify the initial cost of the recursive ray traversal. (..). (..) The total processing time for the ray tracing breaks down into the following components: cell traversal, intersection and shading. Their contributions are depicted in fig.(..), which shows that the intersection is still the major time-consuming activity. The constant time performance is confirmed by the results of fig. (..). Unfortunately, the constant time is constantly very high. (sigh) So far my thesis and exactly what was predicted by Jim. In some test examples (for instance a simple set up with five elementary volumes (a few thousand polygons)) the average number of cells traversed was about 5. The original idea was not to eliminate the number of internal nodes that are traversed (because I use the EXCELL indexing method) but to avoid the cell plane intersections. First I calculate the intersection of the ray with the six bounding planes of the world box. I put xmin, xmax, ymin, ymax, zmin and zmax on a stack and I half each time the ray segment for x, y and z alternatively. Further, while subdividing the ray I also half the directory index range of the EXCELL directory (this requires another filling of the directory than in the original method) and when the range contains only one index then the leaf level has been reached and the ray intersection with the cell data can be done. (If this is unclear I can give a more elaborated explanation next time). It will be clear that I can not use with my method arbitrary partitioning planes. An important point is the actual coding. My implementation was in Pascal and I can imagine much better programs than I can write. ----------------------------------------------------------------------------- from: Jim Arvo subject: some thoughts on the theory of RT efficiency [Jim is writing the course notes on efficiency for the "Introduction to Ray Tracing" course at this year's Siggraph. He sent this on to me and mentioned I could pass them on to all. Enjoy! - EAH] Yes, I did receive the latest RT news with my octree stuff in it. By the way, it occured to me that you mentioned something about walking up an octree to find the nearest common ancestor between a voxel and its neighbor. Olin and I have been discussing this, and I'm quite sure that it's equivalent to the algorithm I described (but it's NOT immediately obvious). The important fact is that neighboring voxels in an octree have a common ancestor which is two steps up (on average) regardless of the depth of the octree. This is what gets rid of the log N factor. With respect to "A Characterization of Ten Ray Tracing Efficiency Algorithms", I'm hoping that my section of the course notes will take a good first step toward filling this need. There's obviously an infinite amount of work to be done here, especially considering that ray tracing is on very shaky theoretical grounds as it stands. Not that we have any doubts that it works! We just can't say anything very convincing about how good our optimizations are at this point. We clearly have to do some of the things you suggested in your last message, or possibly go back to square one and try to create a formal "ray tracing calculus" which we can actually prove things about. And, of course, I agree totally that we need to get a good handle on the strengths of the various techniques in order for something like annealing to have any chance at all. By the way, while writing the course notes I realized that there is a nice connection between the light buffer, the "ray coherence theorem" [Ohta/Maekawa 87], and ray classification. If you start with a "direction cube" (like the hemicube of radiosity) and cross it with (i.e. form the cartesian product with) different "sets", you get the central abstractions which these algorithms are based upon. Like so: light buffer ----- ray coherence theorem ----- ray classification directions directions directions x x x points "objects" "space" This is a very simple observation, but I think it makes the different uses of direction easier to visualize, and certainly easier to explain. All three use sorted object lists associated (directly or indirectly) with "cells" of a subdivided direction cube. I think these three algorithms form a nice well-rounded section on "directional techniques." Well, back to the salt mine... -- Jim --------more I want to get your opinion concerning the correspondence between the light buffer, the "ray coherence" algorithm, and ray classification which I mentioned previously. In particular, I have the following chart which I'd like to include in my section of the course notes and, since the light buffer is your baby, I'd like you to tell me 1) If I've represented it fairly 2) If there are other criteria which you think might be helpful to add to the chart Here is the chart (which is actually just a figure in the context of a more detailed discussion): Light Buffer Ray Coherence Ray Classification ------------ ------------- ------------------ Directions Points Objects Space crossed with (representing (including (bounding the ------------ light sources) light sources) environment) Applied to shadowing rays all rays all rays ---------- Type of polygonal unrestricted unrestricted environment (can be extended) ----------- When data structure preprocessing preprocessing lazily during is built ray tracing --------- Direction uniform uniform adaptive subdivision via quadtree ----------- Construction modified "coherence "object class- of item list polygon ras- theorem" applied ification" using ------------ terization to all pairs of hierarchy of objects beams Parameters number of number of max tree depth, ---------- direction direction max item list size, cells cells truncation size, etc. Item list constant time constant time Traversal of 2D or Lookup 5D hierarchy and --------- caching. Also, have you given any thought to adaptive subdivision or lazy evaluation? Are there other interesting extensions that you'd care to mention? [I still haven't replied - soon! (tonight, if I can help it)] ----------------------------------------------------------------------------- from: Eric Haines Automatic Creation of Object Hierarchies for Ray Tracing -------------------------------------------------------- This document is an explanation of the ideas presented by Goldsmith and Salmon in their May '87 paper in IEEE CG&A. Some changes to their algorithm have been made for additional efficiency during ray tracing (though additional cost for the preprocess). The problem is that you are given a list of objects and wish to create a near optimal hierarchy of bounding volumes to contain these objects. The basic idea is to create the tree as we go, adding each node at whatever location seems most optimal. To avoid searching through the whole tree, we work from the top down and figure out which child branch is most worth looking at. The Algorithm ------------- As G&S note, the form of the tree created is order dependent. One good method of ensuring a better tree is to shuffle the order of the list. This can be done by: given a list of objects OBJ[1..N], for I = 1 to N { R = random integer from 1 to N swap OBJ[I] and OBJ[R] } Given the list of N objects, form bounding boxes for each and calculate the area. The area of the bounding box enclosing an object is proportional to: Probability of hit == P = X*(Y+Z)+Y*Z and this is all we need to calculate, since we're using these areas relative to one another. The first object is considered as a root node of a tree structure, simply: {OBJ[1]} Tree #1 - the initial tree and the other nodes are added to this tree one by one in optimal places. Node Placement -------------- Start with the second node and look at the root of the tree. The root will be either an object or a bounding volume (well, for the second node it will be an object, after that it'll be a bounding volume. We're presenting this algorithm in this fashion because this section will be used recursively throughout the root's children). Root node is an object: In this case, the new object (call it OBJ[2]) will form a binary tree with the root node, as follows. {BV[1]} Tree #2 - adding an object to tree #1 | (First Method) +----------+----------+ | | {OBJ[1]} {OBJ[2]} A bounding volume was created which contains both objects, and the bounding volume became the root node. Root node is a bounding volume: In this case, three different possible paths can be taken when adding a new object to the tree. The first is simply to add a binary tree structure as above, with one child being the old root and the other child being the new object. For example, adding a new object (OBJ[3]) in this fashion to tree #2 above yields: {BV[2]} Tree #3 - Adding object #3 to tree #2 | (First Method) +----------+----------+ | | {BV[1]} {OBJ[3]} | +----------+----------+ | | {OBJ[1]} {OBJ[2]} Again a new bounding volume has been created and made the root node. The second method for adding to a bounding volume root node is to simply add the new object as a new child (leaf) node: {BV[1']} Tree #4 - adding an object to tree #1 | (Second Method) +----------+----------+---------------------+ | | | {OBJ[1]} {OBJ[2]} {OBJ[3]} Note that the bounding volume root node may increase in size. This new bounding volume is noted as BV[1'] to note this possible change. The third method is to not add the new object as a sibling or a child of the root, but rather to add it as a grandchild, great-grandchild or lower. In this case, some child is picked as the most efficient to accomodate the new object. This child then acts like the root node above and the new object is added in the same fashion, by choosing one of the three methods (or, if it is a leaf node, automatically selecting the first method). The next section deals with deciding which method is the most efficient. Selection Process ----------------- The goal behind creating the tree is to minimize the average number of intersection tests which must be performed. By looking at the extra costs added by adding an object at various points we can select the least expensive option. The costs are based on the area of the objects, which represents the probability of the objects being hit by a ray. The scheme is to test what the additional cost is for method one and for method two and record which is better. This cost is termed the "local best cost". For the root node this cost is also saved as the "best cost", and the method and item are also saved. Then method three is used, selecting the child thought to be most efficient for adding the new object. An "inheritance cost" is calculated for method three, which is passed on to the child. This cost is essentially the expense to the parents of adding the object to the tree. It occurs only when the parent bounding volume must increase in size to accomodate the new object. The term "inheritance cost" will mean the cost addition calculated at the level, which is the sum of the "parent inheritance cost", inherited from above, and the "local inheritance cost", the extra cost due to this level. The child selected is then checked for its cost using methods one and two. If the local best cost plus the parent inheritance cost is better than the best cost of earlier parents, the best cost, method, and location are updated. We now check method three to look for an efficient child of this child. If the inheritance cost (which will be the sum of the local inheritance cost found at this level plus the parent inheritance cost from earlier) is greater than the best cost, method three does not have to be pursued further on down the tree. This halting is valid because no matter where the node would be added further down the tree, the cost will never be better than the best cost. Otherwise, this whole procedure continues recursively on down the tree until method three can no longer be performed, i.e. the inheritance cost is higher than the best cost or the selected testing node is an object (leaf) node. At this point, whichever node has been chosen as the best node is modified by method one or two. Note that method three is not a true modification, but rather is just a recursive mechanism, pushing the testing by methods one and two down the tree. After performing the changes to the tree structure, the parent boxes are increased in volume (if need be) to accomodate the new object. Efficiency Criteria ------------------- Well, we've been talking in a vacuum up to now about how to calculate the average number of ray intersections performed for a tree. We perform the same calculations as G&S to determine the average--see that article for a good explanation. We also take their advice and not worry about the probability of hitting the root node, and so multiply our probability equation by the proportional volume of the root node. The practical effect is that this avoids a number of pointless divisions, since we just want to calculate relative costs of adding the object to the structure and don't really want the actual average ray/tree intersection value. The cost for method one: what happens here is that a bounding volume is created and its two children are the original test node and the new object. We will use trees #1 and #2 to derive the cost calculations. The initial probability cost of hitting OBJ[1] are simply: old cost = 1 This is the because the topmost node is always tested. The new probability cost is the cost of hitting the bounding volume and intersecting the two objects inside the bounding volume. Essentially: new cost = 1 + 2 * P(BV[1]) This formula can be interpreted as follows. One ray intersection is done to intersect the bounding volume. If this volume is hit, two more ray intersection tests must be done to check the two objects contained within. From these two equations we can calculate the difference, which is: cost difference = 2 * P(BV[1]) The cost for method two: what happens here is that the new object is added to the existing bounding volume. Using trees #2 and #4 for demonstration, the old cost is: old cost = 1 + k * P(BV[1]) where k is the number of children (in our example, it's 2). The new cost is: new cost = 1 + (k+1) * P(BV[1']) with P(BV[1']) being the new area of the bounding volume. The difference is: cost difference = ( P(BV[1']) - P(BV[1]) ) * k + P(BV[1']) The inheritance cost for method three: the cost incurred will be the difference between intersecting children times the old parent's area and intersecting children times the new parent's volume. The old cost is: old cost = 1 + k * P(BV[1]) The number of children is the same for the new cost (i.e. the new object will be added on down the line by method one or two, which always ends up with one root node), so the only thing that can change is the volume: new cost = 1 + k * P(BV[1']) The difference: cost difference = ( P(BV[1']) - P(BV[1]) ) * k With these criteria in hand, we can now actually try the method out. Example ------- There are four tiles of a checkerboard to be ray traced, which, after shuffling, are as shown: +---+---+ | 1 | 3 | +---+---+ | 4 | +---+ | 2 | +---+ We start with a tree consisting of tile #1, with area 1. Adding tile #2, we automatically come up with a tree: BV* (area 3) | +--------+----------+ | | 1 (area 1) 2 (area 1) Note: BV* means the new BV being added, BV' means an old BV possibly increasing in size. Looking at tile #3, we try out method one: BV* (area 6) | +----------+----------+ | | BV (area 3) 3 (area 1) | +--------+----------+ | | 1 (area 1) 2 (area 1) The cost difference is simply 2 times the new BV area, i.e. 12. We also look at the cost of method 2: BV' (area 6) | +-------------------+---------------------+ | | | 1 (area 1) 2 (area 1) 3 (area 1) The cost is (new area - old area) * 2 children + new area = (6-3)*2 + 6 = 12. Since this is the same as method one, either method one or method 2 can be selected, with the best cost being 12. Method 3 is now applied, looking at each child and using methods one and two on them. The inheritance cost is (new area - old area) * 2 children = (6-3)*2 = 6. Each child is an object (leaf) node, so only method one can be used. Trying this on object 1: BV' (area 6) | inheritance = 6 +----------+----------+ | | BV* (area 2) 2 (area 1) | +--------+----------+ | | 1 (area 1) 3 (area 1) The local cost is 2 * new area, i.e. 4. The cost including the inheritance is 4 + 6 = 10, which is lower than our earlier best cost of 12, so performing method one on object 1 is now the best solution. Trying method 1 on object 2 we get: BV' (area 6) | inheritance = 6 +----------+----------+ | | 1 (area 1) BV* (area 6) | +----------+----------+ | | 2 (area 1) 3 (area 1) The increase in cost is 2 * new area, i.e. 12. This plus the inheritance of 6 is 18, which is certainly horrible (as we would expect). So, we end out with the best solution being replacing the node for object 1 with a BV which contains objects 1 and 3, shown earlier. For object 4, we again test method one: BV* (area 6) | +----------+----------+ | | BV (area 6) 4 (area 1) | +----------+----------+ | | BV (area 2) 2 (area 1) | +--------+----------+ | | 1 (area 1) 3 (area 1) The local cost is 2 * new area, i.e. 12. Trying out method two: BV (area 6) | +---------------------+---------------------+ | | | BV (area 2) 2 (area 1) 4 (area 1) | +--------+----------+ | | 1 (area 1) 3 (area 1) The cost is (new area - old area) * 2 children + new area = (6-6)*2 + 6 = 6. This is the better of the two methods, so method two applied to the root is noted as the best cost of 6. Method 3 is now applied, looking at each child and using methods one and two on them. The inheritance cost is (new area - old area) * 2 children = (6-6)*2 = 0. The first child is the BV containing objects 1 and 3, so we try method 1: BV (area 6) | inheritance = 0 +----------+----------+ | | BV* (area 4) 2 (area 1) | +----------+----------+ | | BV (area 2) 4 (area 1) | +--------+----------+ | | 1 (area 1) 3 (area 1) The cost is 2 * new area + inheritance = 8, which is not better than our previous best cost of 6. Method two yields: BV (area 6) | inheritance = 0 +----------+----------+ | | BV' (area 4) 2 (area 1) | +---------------------+---------------------+ | | | 1 (area 1) 3 (area 1) 4 (area 1) The cost is (new area - old area) * 2 children + new area = (4-2)*2 + 4 = 8, which, plus the inheritance cost of 0, is not better than our previous best cost of 6. Now we try method one on the second node of the tree, i.e. object 2: BV (area 6) | +--------------------+--------------------+ | | BV (area 2) BV* (area 2) | | +--------+----------+ +----------+----------+ | | | | 1 (area 1) 3 (area 1) 2 (area 1) 4 (area 1) Again, the cost is 2 * new area + inheritance = 2 * 2 + 0 = 4. This beats our best cost of 6, so this is the optimal insertion for object 4 so far. Since this cost is also better than the best cost of 8 for the first child, this branch is the best child to pursue further on down (though we can't go further). This means that we do not have to try methods one for object 4 on the first child's children (objects 1 and 3). Confused? Well, that's life. Try examples of your own to see how the algorithm works. Improvements ------------ G&S say they check which child node will be tested further by which has the smallest increase in area when the new object is added to it. In case of ties (which occur mostly when the area doesn't increase at all), they give a few possible sub-criteria for choosing. However, by the logic of bounding volumes, the real test that should be done is to pick the bounding volume which gives the best result when methods one and two are applied to it. To prove this by example, imagine a bounding volume containing two other bounding volumes, one huge (say it has 50% of the area of its parent) and one tiny (say it's 1%). Let's say an object is inserted which would not increase the size of the 50% BV but would triple the size of the 1% BV to 3%. By Goldsmith's criterion we must pick the 50% BV to insert the object into. Now if we intersect the root node we will hit the 50% BV half the time, and so must then do the other object intersection half the time. If instead we had picked the 3% BV, this would be hit 3% of the time, meaning that we would have to do the object test only 3% of the time. In both cases we had to test each BV, but it was smarter of us to put the object in the smaller BV in order to avoid testing. This case will be caught by testing the increases for methods one and two for the BV's. Method one for the larger would yield 50%*2 and method two 50%*1, giving 50% as the best cost. For the tiny BV, method one yields 3%*2 = 6% and method two (3%-1%)*2 + 3% = 7%, giving 6% as the best cost, obviously much better. Even though we have increased the chance of having to open the smaller box, it's still cheaper to do this than to add the object to a box which is much more likely to be hit. ----------------------------------------------------------------------------- Best of USENET: From: cyrus@hi.unm.edu (Tait Cyrus) Newsgroups: comp.graphics Subject: images Organization: U. of New Mexico, Albuquerque It seems that once a month someone asks where they can get ahold of some images to play with. Well, for those of you looking for images to "play" with, I have some images available that you can have. They are available via anonymous ftp on hc.dspo.gov (26.1.0.90). The images are in pub/images. There are two directories 'old' and 'new'. Both contain images as well as a README. The README's describe the sizes of the images and basically what the images are of. Because of disk space constraints, all of the images are compressed. All of the images, but one, are grey scale. The other is an image of a mandrill in color. Three files make up the madrill, one for green, red and blue. Currently there are 20 images. As time goes on this number will be increasing (I hope), so if you are interested in images, you might want to check once a month or so to see if there are any new ones. If you have any images which you would like to make available, please let me know. I would like to put them with the ones I currently have (kind of like a repository). More: Several people have asked me for some more details concerning the images I have made available on hc.dspo.gov (26.1.0.90). Again, the images are available via anonymous ftp and are in /pub/images. There are 2 directories, 'new' and 'old' which contain the 20 or so images. Both have README's which describe the images and the sizes of the images. The images are compressed, the README's are NOT. If your system does not have uncompress (you might check with your system manager first to make sure) I have put the source for compress/uncompress in /pub of the same machine. The images are all grey scale, except for mandrill. The grey scale images are such that each pixel is represented by one byte (value of 0 = black, 255 = white). Hope this helps any of you who were confused or were having troubles. >From: todd@utah-cs.UUCP (Todd Elvins) Newsgroups: comp.graphics Subject: New model of an espresso maker Organization: University of Utah CS Dept I have installed a file called 'espresso.polys' on the ftp directory at cs.utah.edu It is a model of one of those aluminum italian made espresso makers. T. Todd Elvins IFSR ({ucbvax,ihnp4,decvax}!utah-cs!todd, todd@cs.utah.edu) "Eat, drink, and be merry, for tomorrow you might be in Utah." END OF RTNEWS _ __ ______ _ __ ' ) ) / ' ) ) /--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _ / \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_</_(_(_/_/_)_ / /| ' |/ "Light Makes Right" June 20, 1988 Compiled by Eric Haines, 3D/Eye Inc, ...!hplabs!hpfcla!hpfcrs!eye!erich All contents are US copyright (c) 1988 by the individual authors Contents: New people and addresses (David Lister, Pete Segal, Paul Heckbert) Non-article on RenderMan and Dore' (Eric Haines) Ray Tracing Bibliography Update (Paul Heckbert & Eric Haines) Commercial Ray Tracing Software (Eric Haines) Benchmarks (Jeff Goldsmith) So, I've regained the desire to type again a mere month after the SIGGRAPH course notes deadlines. Not much in the queue, but I thought I'd pass on what little there is. The most interesting developments which affect ray tracing are the release of the RenderMan (tm) interface by Pixar and the publication of Ardent's Dore' (tm) Programmer's Guide and Reference Manual. Andrew Glassner's hardcopy "RT News" is coming out soon - if you're not on the mailing list, write him. SIGGRAPH Ray Tracers Roundtable: in case you don't know, this is an informal get-together during SIGGRAPH where we talk about ray tracing techniques and trends. Personally, I'd like to aim for about the same time as last year: Thursday, sometime after 5 pm (with people then hitting the technical reception for food afterwards). Same as last year, we'll leave notes at the message center to all subscribers as to exactly where and when. If you're not planning to attend SIGGRAPH, please save me some note-writing effort by telling me. Otherwise, see you there. ----------------------------------------------------------------------------- New people and addresses ------------------------ Paul Heckbert's summer address (at Xerox PARC): heckbert.pa@xerox.com Mail will still (slowly but surely) reach Paul at his old Berkeley address. # David Lister # Data General Corp. # 62 T. W. Alexander Drive # Research Triangle Park, NC 27709 # (919) 248-6223 alias david_lister hpfcrs!hpfcla!hplabs!lister@dg-rtp.dg.com From David: I have been working on Ray Tracing since 1984 while I was a graduate student at The Ohio State University. I am still working on my thesis for my MSEE on parallelism and algorithm improvements for Ray Tracing. My areas of Ray Tracing interest include the following: 1). algorithm efficency 2). simulation of natural phenomenon (optical characteristics of materials) and, 3). parallelism. David Lister # Pete Segal # AT&T Pixel Machines # Room 4K-208 # Crawfords Corner Road # Holmdel, NJ 07733 # (201)-949-1244 alias pete_segal hpfcrs!hpfcla!ihnp4!homxc!pixels!pls From Pete: I'm not real big on introductions, but here goes... I was born the son of a poor black sharecropper... wait, wrong story.... I started in the Computer graphics lab at RPI in 1979, got my Master's in '82 and came to Bell Labs doing graphics for CAD systems. I moved to Pixel Machines in early 1987 and have been working there since. I am interested in 3d rendering and animation, and I am currently working on the Ray tracing library for the Pixel Machine, RAYlib. ----------------------------------------------------------------------------- Non-article on RenderMan and Dore' (by Eric Haines) What follows is a non-review of RenderMan and Dore'. If you've been looking for a chance to contribute to the RT News, here's your chance - I'm not planning on reviewing either of these in depth, but would love to hear others' opinions (even anonymous ones) of these packages. I just received a copy of Pixar's "RenderMan" interface. To quote the preface: The RenderMan interface is designed so that the information needed to specify a photorealistic image can be passed to different rendering programs compactly and efficiently. ... In order to achieve this, the interface does not specify how a picture is rendered, but instead what picture is desired. ... The RenderMan interface is a collection of procedures to transfer the description of a scene to the rendering program. The interface for the ray tracer is wonderfully short, as it is simply another command in Pixar's shading language. I include it here in full: 18.4.5 RAY TRACING color trace( point R ) "trace" returns the incident light falling on a surface in a given direction R. If a particular implementation does not support ray tracing, and cannot compute the incident light arriving from an arbitrary direction, trace will return 0 (black). That's it. I don't see any way this command can support shadowing or filtering, but I haven't read through the document carefully (Pixar seems to want to go with their "Shadow Depth Maps" instead - SIGGRAPH 87 paper). Anyway, this interface is "endorsed" by Apollo, DEC, Stellar, Ardent, and Sun, so it seems to be a happening something. I'm not sure what "endorsement" means, exactly, but one thing it means is that you should probably check it out. Dore': well, I received the two preliminary manuals yesterday. As such, about all I can commit myself to is: "nice packaging - very artsy binders". Reviews, please? ----------------------------------------------------------------------------- Ray Tracing Bibliography Update (Paul Heckbert & Eric Haines) Paul Heckbert's "Ray Tracing Bibliography" has been updated for May, 1988. It will appear in the next issue of the hardcopy "Ray Tracing News" and in the SIGGRAPH '88 "Introduction to Ray Tracing" course notes. If you would like to see it before then, or would just like to have an electronic version on hand, please write Eric Haines and I'll mail you the latest version. Also, if you do get a copy, please tell us of any errata or addenda you may have for it. ----------------------------------------------------------------------------- Commercial Ray Tracing Software, by Eric Haines ------------------------------- I'm collecting information for the "Consumer's and Developer's Guide to Image Synthesis" course at SIGGRAPH this year - namely, companies selling ray tracers. The bare bones info is at the end of this issue. I'm in the midst of ordering manuals, but that's about as far as I'm going. So, I would like to hear from anyone who knows anything about these packages. I will keep all reviews confidential, unless you explicitly state otherwise. Below is a partial list of groups (in alphabetical order) offering ray tracing packages. If you know of any others, please clue me in (I'm particular ignorant when it comes to software for animators & advertising, such as Wavefront. For now, I have left them off the list below). The "Contact" section first lists the person who I have dealt with, followed by the official contact address and/or phone number. I believe the only company that won't have representation on the floor at SIGGRAPH is Ray Tracing Corp (though UCS probably will, in some form). Oh, just to dispell rumors, "Numerical Designs Ltd", Turner Whitted's company, is not planning on announcing a ray tracer by SIGGRAPH 88. Instead, they are marketing a package based on using pipes and filters for rendering (beyond this, I do not know...). AT&T, Pixel Machines "RAYlib". Available only on the Pixel Machine. Cost: ???, manuals available realsoonnow. Contact: Ken Krause, 201-563-2274. AT&T Pixel Machines 1-800-544-0097 Ardent, "Dore'". Available on Ardent's Titan superworkstation. Source available in C, portable to other machines. Cost: $250 for universities, research sites. $15000/$5000 per year for commercial sites. Binary license $200 per copy. Programmer's Guide and Reference Manual preliminary versions are $25 each. Contact: Ardent Computer Corporation, 880 West Maude Avenue, Sunnyvale, CA 94086 408-732-0400 Hewlett Packard. Add-on to their existing "Starbase" graphics package, which will also include radiosity software. Announced at NCGA 1988. Available with the TurboSRX come the end of the year (?). Cost: ??? Contact: Hewlett Packard Co. 1-800-752-0900, Ext. 782A Integra (via Mitsubishi, via Enimax), "Turbo Beam Tracing". Available on IBM PC/AT or compatible. Cost: ??? (will be shown at SIGGRAPH) Contact: Gregory Szewczyk Enimax International Inc. 113 Martin Grove Road Etobicoke, Ontario M9B 4K7 CANADA 416-234-9120 Ray Tracing Corp, "TRACER" and "TRACER PC". Source available in FORTRAN 77. "TRACER" runs on Cray, VAX, and many Unix-based systems. "TRACER PC" is for the IBM PC, 640K memory, 20 Mb hard disk, math co-processor, and Targa or Number Nine card. "TRACER PC" includes a modeler. Cost: $3000 for source and first year of updates. Manual for $25. Contact: Mark Franklin Ray Tracing Corporation 2516 Via Tejon, Suite 316 Palos Verdes Estates, CA 90274 213-373-0520 United Computer Systems, Inc, "Ray Tracer". Available on Apollo, IBM, and Mac. Evidentally selling well on Mac and IBM: 4x sales than Apollo sales since intro post-SIGGRAPH '87. It turns out that this product is actually made by Ray Tracing Corp. Cost: ???, manual available for $25. Contact: Alan Brown (at TMAC (sp?)), 213-475-1067 United Computer Systems, Inc Graphics Development Group 10564 Progress Way Cypress, CA 90630 714-220-2931 Wavefront Technologies, Inc, "3-D Dynamic Imaging System". Their system has "production speed ray tracing" as a feature. Cost: ??? Contact: Wavefront Technologies 530 East Montecito Street Santa Barbara, CA 93103 (805)-962-8117 ----------------------------------------------------------------------------- Benchmarks, by Jeff Goldsmith [This recently appeared in the email newsletter on scientific visualization that Jeff Goldsmith has been editing. If you're interested in subscribing and contributing to the SciVi discussion group, contact him at: jeff@hamlet.caltech.edu . I thought it of interest because of the bounding box intersector statistics. - EAH] I did an interesting micro-project this winter/spring. We were interested in porting some programs to PCs and/or Workstations, so I compared the performance of a few chunks of graphics code on a bunch of machines. The code was supposed to represent some of the typical cpu and I/O intensive things that graphics programs tend to do. The benchmarks are: Faults: randomly accesses a huge array (>16 Megabytes) (I know--not huge to you Cray users, but it is to PCs) Obviously, tests virtual memory usage. Shade: typical shading routine. Tests floating point very strongly. Bbox: highly optimized bounding box intersection routine for a ray tracer. (actually, this one has become somewhat unoptimized for the testing, but you get the idea) Was intended to test floating point performance and if-then-else branching. Actually, tests floating point and caching. Clear: sequentially clears a large memory array. Tests compiler, MIPS, and memory usage. Sub: calls an empty subroutine repeatedly. Tests MIPS. Fread: formatted reads and writes. Tests I/O speed, floating point performance and MIPS. Uread: binary reads and writes. Tests raw I/O speed. Machine faults shade bbox clear sub fread uread ------- ------ ----- ---- ----- --- ----- ----- VAX780 12.5 16.9 12.3 11.8 19.3 17.4 23.2 uVAX II 22.2 18.5 15.6 12.9 18.9 24.0 29.1 HP320 * 10 45 4 8 5 6 HP350 4 5 28 3 4 3 4 Sun 3/1 * 9 34 4 6 5 5 Sun 3/2 * 9 48 3 3 2 4 Sun 386 * 9.5 16 2 5 3 1 Mac II * 31.3 44.3 * 4.3 13 5.3 PC/AT * 70 180 * 39 17 6 PS 2/80 * 9.4 49.7 * 11.1 11.4 7.3 Compaq ~ ~ ~ ~ 19.0 13.1 5.5 Iris * 30 59 4 5 15 3 IrisFPA * 11 13 4 5 6 3 All entries are in seconds to run specified benchmark. * indicates that operating system not set up to allow program to run. ~ indicates benchmark not attempted. The machines tested: VAX780: Vax 11/780 with FPA and 32 Mbytes memory uVAX II: Microvax II, VMS, 16 Mbytes memory HP320: Unix HP350: SRX, Unix, 32 Mbytes memory Sun 3/1: Sun 3/160, 68881 co-processor Sun 3/2: Sun 3/260, 68881 co-processor Sun 386: Sun 386i/250, 80386/80387, Unix Mac II: MPW, 68881 PC/AT: Xenix, 80287 PS 2/80: OS2, 80387 co-processor Compaq: Compaq 386, Unix, no coprocessor Iris: SGI IRIS 3030 without FPA IrisFPA: SGI IRIS 3030 with FPA (Iris 3130 performance was identical to 3030.) What did I learn from all this? One thing is obvious: if a FPA is available for your machine and you can afford it (they are usually cheap) buy it even if you don't do alot of floating point. It affects all sorts of performance characteristics. Another important point: it is not possible to evaluated computer performance as one number. Different computers do different things well. ----------------------------------------------------------------------------- END OF RTNEWS